package LeetCode._01_树;

public class _124_二叉树中的最大路径和 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
       if(root == null) return 0;
       traverser(root);
       return res;
    }

    //计算从根节点root为起点的最大单边路径和
    public int traverser(TreeNode root){
       if(root == null) return 0;

       int leftPathMaxSum =Math.max(0,traverser(root.left));
       int rightPathMaxSum =Math.max(0,traverser(root.right));

       int pathMaxSum = root.val + leftPathMaxSum + rightPathMaxSum;
       res = Math.max(pathMaxSum,res);

       return Math.max(leftPathMaxSum,rightPathMaxSum) + root.val;
    }
}
